package cn.yuemouren.suanfa;

/**
 * @Author: Timi
 * @Description: 归并排序
 * @Date: 2020/7/23 15:37
 */
public class MergeSort {

    public static void main(String[] args) {
        int[] arr = {1,7,2,4,5,8,15,9};
        mergeSort(arr);
        print(arr);
    }

    private static void mergeSort(int[] arr){
        sort(arr,0,arr.length - 1);
    }

    private static void sort(int[] arr,int left,int right){
        //终止条件
        if(left >= right)
            return;
        //寻找中间值
        int mid = (right + left) / 2;

        //递归对数组左边
        sort(arr,left,mid);

        //递归对数组右边
        sort(arr,mid + 1,right);

        //对数组进行合并
        merge(arr,left,mid,right);

        print(arr);
    }

    private static void merge(int[] arr,int left,int center,int right){
        //新建一个临时数组
        int[] tempArr = new int[arr.length];
        //右边索引开始
        int mid = center + 1;
        //临时数组的索引
        int third = left;
        //记录左边第一个索引开始
        int tmp = left;

        while(left <= center && mid <= right){
            //比较左右两边较小的放入临时数组中
            if(arr[left] <= arr[mid]){
                tempArr[third++] = arr[left++];
            } else {
                tempArr[third++] = arr[mid++];
            }
        }

        //右边还有剩余加入临时数组
        while(mid <= right){
            tempArr[third++] = arr[mid++];
        }

        //左边还有剩余加入临时数组
        while(left <= center){
            tempArr[third++] = arr[left++];
        }

        //将临时数组中的元素拷回到原数组中
        while(tmp <= right){
            arr[tmp] = tempArr[tmp++];
        }
    }

    private static void print(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + "\t");
        }
        System.out.println();
    }
}
